This specification is directed generally to ranking query suggestions for a partial query, and more particularly, to ranking query suggestions based on aspects of media files that have been provided to a user. A user may begin to enter a search query and desire to have suggestions that are based on the entered partial query to be provided. Search query suggestions may be selected based on the similarity between the entered partial query and a query suggestion. Query suggestions may be ranked based on the likelihood that a query suggestion is the query suggestion that the user is entering. A query suggestion engine may increase the accuracy of ranking query suggestions based on information that is specific to the user that entered the partial query. For example, a query suggestion engine may suggest and/or rank query suggestions based on previous search queries of the user.